import javax.print.DocFlavor;
import java.util.*;

class Person {
    public String id;

    public Person(String id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class Test2 {

    //https://leetcode.cn/problems/contains-duplicate/
    //存在重复元素
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;

    }

    //https://leetcode.cn/problems/contains-duplicate-ii/
    //存在重复元素2
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (map.containsKey(num) && i - map.get(num) <= k) {
                return true;
            }
            map.put(num, i);
        }
        return false;


    }

    //https://leetcode.cn/problems/top-k-frequent-words/description/
    //前K个高频单词
    public List<String> topKFrequent(String[] words, int k){
        HashMap<String,Integer> map = new HashMap<>();
        //首先先统计每个单词出现的次数
        for (String word : words) {
            if (map.get(word) == null){
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }

        //接着建立小跟堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //再遍历map
        for (Map.Entry<String,Integer> entry : map.entrySet()){
            if (minHeap.size() < k){
                minHeap.offer(entry);//说明小跟堆还没建好
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if (top.getValue().compareTo(entry.getValue()) == 0){
                    if (top.getKey().compareTo(entry.getKey()) > 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        ArrayList<String> list = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp =minHeap.poll();
            list.add(tmp.getKey());
        }//将前K个单词存入list中

        //由于是小跟堆，所以顺序不是从高频率到低频率 则将list逆序一下
        Collections.reverse(list);
        return list;

    }

    //https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
    //坏键盘打字
    public static void func(String str1,String str2){
        str1 = str1.toUpperCase();//将所有字母转化成大写
        str2 = str2.toUpperCase();

        HashSet<Character> setAct = new HashSet<>();
        for (int i = 0; i < str2.length(); i++) {
            char ch = str2.charAt(i);
            setAct.add(ch);
        }//把能打印的字符都存放到setAct内

        HashSet<Character> setBroken = new HashSet<>();//存放打印不出来的字符，这样可以避免重复

        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if (!setAct.contains(ch) && !setBroken.contains(ch)){
                setBroken.add(ch);
                System.out.print(ch);
            }
        }
    }

    public static void main4(String[] args) {
        func("7_This_is_a_test","_hs_s_a_es");//7TI
    }

    //https://leetcode.cn/problems/jewels-and-stones/
    //石头与宝石
    public int numJewelsInStones (String jewels,String stones){
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            set.add(ch);
        }

        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);
            if (set.contains(ch)){
                count++;
            }
        }
        return count;
    }


    //https://leetcode.cn/problems/copy-list-with-random-pointer/
    //随机链表的复制
    class Node{
        int val;
        Node next;
        Node random;

        public Node(int val){
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head){
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);//老节点 新节点
            cur = cur.next;
        }
        cur = head;//遍历一遍后，让cur回到开头 重新进行遍历
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }


//    public static void main(String[] args) {
//        int i=10;
//        HashSet<Integer> set = new HashSet<>();
//        set.contains(i);
//    }

    //https://leetcode.cn/problems/single-number/
    //只出现一次的数字
    public int singleNumber(int[] nums){
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                set.remove(nums[i]);
            }else {
                set.add(nums[i]);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;
    }


    //统计单词出现的次数
    public static Map<String,Integer> countWord(String[] words){
        Map<String,Integer> map = new HashMap<>();
        for (String s : words){
            if (map.get(s) == null){
                map.put(s,1);
            }else {
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        return map;
    }

    public static void main3(String[] args) {
        String[] words = {"hello","abc","hello","def","this","this","this"};
        Map<String,Integer> map = countWord(words);
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        for (Map.Entry<String,Integer> entry : entrySet) {
            System.out.println("key: "+ entry.getKey()+ "val: "+ entry.getValue());
        }
    }


    public static void main2(String[] args) {
        Person person1 = new Person("1234");
        Person person2 = new Person("1234");

        /*System.out.println(person1.hashCode());
        System.out.println(person2.hashCode());

        System.out.println(person1.equals(person2));*/
        HashBuch2<Person,String> hashBuck2 = new HashBuch2<>();
        hashBuck2.push(person1,"xiaoming");

        System.out.println(hashBuck2.getVal(person2));

    }
    public static void main1(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.push(1,111);
        hashBuck.push(11,111111);
        hashBuck.push(14,141414);
        hashBuck.push(4,444);
        hashBuck.push(2,222);
        hashBuck.push(15,151515);
        hashBuck.push(6,666);
        hashBuck.push(5,555);

        System.out.println(hashBuck.getVal(15));

    }
}
